import java.util.Arrays;
public class myArrayList implements IArrayListOperation{
    //顺序表的底层是由一个动态可扩容的数组+计数器组成
    private int[] elem;
    private int usedSize;
    private static final int DEFAULT_CAPACITY = 10;
    public myArrayList() {
        this.elem = new int[DEFAULT_CAPACITY];
        this.usedSize = 0;
    }
    public myArrayList(int capacity) {
        if(capacity <= 0) {
            try{
                throw new MemoryIsEmptyException("内存参数非法，已构造默认参数！ 非法参数："+capacity);
            }catch(MemoryIsEmptyException e) {
                capacity = DEFAULT_CAPACITY;
            }
        }
        this.elem = new int[capacity];
        this.usedSize = 0;
    }

    //新增元素，默认尾插 时间复杂度O（1）
    @Override
    public void add(int data) {
        //判满 满则扩容
        if(isFull()) {
            dilatation();
        }
        //在usedSize处插入
        this.elem[this.usedSize++] = data;
    }

    //在 pos 位置新增元素 时间复杂度O（N）
    @Override
    public void add(int pos, int data) {
        //当pos小于0 或 pos大于数组长度时，pos非法，抛异常
        if(pos<0 || pos>this.usedSize) {
            try{
                throw new MemoryIsEmptyException("pos位置非法！ pos："+pos);
            }catch(MemoryIsEmptyException e) {
                return;
            }
        }
        for(int i = this.usedSize; i > pos; i--) {
            this.elem[i] = this.elem[i-1];
        }
        this.elem[pos] = data;
        this.usedSize++;
    }

    // 判定是否包含某个元素 时间复杂度O（N）
    @Override
    public boolean contains(int toFind) {
        //顺序表为空时不包含
        if(isEmpty()) {
            return false;
        }
        for(int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }

    // 查找某个元素对应的位置 时间复杂度O（N）
    @Override
    public int indexOf(int toFind) {
        if(isEmpty()) {
            try{
                throw new MemoryIsEmptyException("顺序表为空，无法进行查找！");
            }catch(MemoryIsEmptyException e) {
                return -1;
            }
        }
        for(int i = 0; i < this.usedSize; i++) {
            if(this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }

    // 获取 pos 位置的元素 时间复杂度O（1）
    @Override
    public int get(int pos) {
        if(isEmpty()) {
            try{
                throw new MemoryIsEmptyException("顺序表为空，无法进行查找！");
            }catch(MemoryIsEmptyException e) {
                return -1;
            }
        }
        if(pos<0 || pos>=this.usedSize) {
            try{
                throw new MemoryIsEmptyException("pos位置非法！ pos："+pos);
            }catch(MemoryIsEmptyException e) {
                return -1;
            }
        }
        return this.elem[pos];
    }

    // 给 pos 位置的元素设为 value 时间复杂度O（1）
    @Override
    public void set(int pos, int value) {
        if(isEmpty()) {
            try{
                throw new MemoryIsEmptyException("顺序表为空，无法进行设置！");
            }catch(MemoryIsEmptyException e) {
                return;
            }
        }
        if(pos<0 || pos>=this.usedSize) {
            try{
                throw new MemoryIsEmptyException("pos位置非法！ pos："+pos);
            }catch(MemoryIsEmptyException e) {
                return;
            }
        }
        this.elem[pos] = value;
    }

    //删除第一次出现的关键字key 时间复杂度O（N）
    @Override
    public void remove(int toRemove) {
        if(isEmpty()) {
            try{
                throw new MemoryIsEmptyException("顺序表为空，无法进行设置！");
            }catch(MemoryIsEmptyException e) {
                return;
            }
        }
        int index = indexOf(toRemove);
        if(index == -1) {
            System.out.println("抱歉！顺序表中不存在该值！");
        } else{
            for(int i = index; i < this.usedSize-1; i++) {
                this.elem[i] = this.elem[i+1];
            }
            this.usedSize--;
        }
    }

    // 获取顺序表长度 时间复杂度O（1）
    @Override
    public int size() {
        return this.usedSize;
    }

    //清空顺序表 时间复杂度O（1）
    @Override
    public void clear() {
        this.usedSize=0;
    }

    //打印顺序表 时间复杂度O（N）
    @Override
    public void display() {
        for(int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i]+" ");
        }
    }

    //判满
    private boolean isFull() {
        //当有效元素==数组长度 代表满！
        return this.usedSize==this.elem.length;
    }

    //二倍扩容
    private void dilatation() {
        this.elem = Arrays.copyOf(this.elem,this.elem.length*2);
    }

    //判空
    private boolean isEmpty() {
        return this.usedSize==0;
    }
}
